#ifndef GRAPH_H_
#define GRAPH_H_

#include "common.h"

namespace masugo
{

template<typename VertexKeyType, typename VertexValueType, typename EdgeValueType>
class Graph
{
public:
	typedef VertexKeyType VertexKey;
	typedef VertexValueType VertexValue;
	typedef EdgeValueType EdgeValue;

	struct Vertex
	{
		typedef std::tr1::unordered_map<VertexKey, EdgeValue> Adjacency;

		VertexValue value;
		Adjacency adjacency;
	};

	typedef std::tr1::unordered_map<VertexKey, Vertex> Vertices;

	typedef std::pair<VertexKey, VertexKey> VertexKeyPair;
	typedef std::pair<EdgeValue, VertexKeyPair> Edge;
	typedef std::deque<Edge> Edges;

	Graph()
	{
	}

	const Vertices& vertices() const
	{
		return vertices_;
	}

	bool vertex_exists(const VertexKey& vertex_key) const
	{
		return (vertices_.find(vertex_key)!=vertices_.end());
	}

	bool empty() const
	{
		return vertices_.empty();
	}

	bool connected(const VertexKey& vertex_a_key, const VertexKey& vertex_b_key) const
	{
		typename Vertices::const_iterator vertex_a_it=vertices_.find(vertex_a_key);
		if(vertex_a_it!=vertices_.end())
		{
			const Vertex& vertex_a=vertex_a_it->second;
			return vertex_a.adjacency.find(vertex_b_key)!=vertex_a.adjacency.end();
		}
		else { return false; }
	}

	const Vertex& vertex(const VertexKey& vertex_key) const
	{
		typename Vertices::const_iterator vertex_it=vertices_.find(vertex_key);
		if(vertex_it==vertices_.end()) { throw std::invalid_argument(utilities::ParametricString("Function {} misses vertex {}").arg(__FUNCTION__).arg(vertex_key).str()); }
		return vertex_it->second;
	}

	EdgeValue connection_value(const VertexKey& vertex_a_key, const VertexKey& vertex_b_key) const
	{
		typename Vertices::const_iterator vertex_a_it=vertices_.find(vertex_a_key);
		if(vertex_a_it==vertices_.end()) { throw std::invalid_argument(utilities::ParametricString("Function {} misses first vertex {}").arg(__FUNCTION__).arg(vertex_a_key).str()); }
		const Vertex& vertex_a=vertex_a_it->second;
		typename Vertex::Adjacency::const_iterator connection_it=vertex_a.adjacency.find(vertex_b_key);
		if(connection_it==vertex_a.adjacency.end()) { throw std::invalid_argument(utilities::ParametricString("Function {} misses connection between vertices {} and {}").arg(__FUNCTION__).arg(vertex_a_key).arg(vertex_b_key).str()); }
		return connection_it->second;
	}

	void set_vertex_value(const VertexKey& vertex_key, const VertexValue& vertex_value)
	{
		vertices_[vertex_key].value=vertex_value;
	}

	void connect(const VertexKey& vertex_a_key, const VertexKey& vertex_b_key, const EdgeValue& edge_value)
	{
		if(vertex_a_key!=vertex_b_key)
		{
			typename Vertices::iterator vertex_a_it=vertices_.find(vertex_a_key);
			if(vertex_a_it==vertices_.end()) { throw std::invalid_argument(utilities::ParametricString("Function {} misses first vertex {}").arg(__FUNCTION__).arg(vertex_a_key).str()); }
			typename Vertices::iterator vertex_b_it=vertices_.find(vertex_b_key);
			if(vertex_b_it==vertices_.end()) { throw std::invalid_argument(utilities::ParametricString("Function {} misses second vertex {}").arg(__FUNCTION__).arg(vertex_b_key).str()); }
			vertex_a_it->second.adjacency[vertex_b_key]=edge_value;
			vertex_b_it->second.adjacency[vertex_a_key]=edge_value;
		}
	}

	void disconnect(const VertexKey& vertex_a_key, const VertexKey& vertex_b_key)
	{
		typename Vertices::iterator vertex_a_it=vertices_.find(vertex_a_key);
		if(vertex_a_it!=vertices_.end())
		{
			typename Vertices::iterator vertex_b_it=vertices_.find(vertex_b_key);
			if(vertex_b_it!=vertices_.end())
			{
				vertex_a_it->second.adjacency.erase(vertex_b_key);
				vertex_b_it->second.adjacency.erase(vertex_a_key);
			}
		}
	}

	void remove_vertex(const VertexKey& vertex_key)
	{
		typename Vertices::const_iterator vertex_it=vertices_.find(vertex_key);
		if(vertex_it!=vertices_.end())
		{
			const Vertex v=vertex_it->second;
			vertices_.erase(vertex_it);
			for(typename Vertex::Adjacency::const_iterator it=v.adjacency.begin();it!=v.adjacency.end();it++)
			{
				typename Vertices::iterator vertex_b_it=vertices_.find(it->first);
				assert(vertex_b_it!=vertices_.end());
				vertex_b_it->second.adjacency.erase(vertex_key);
			}
		}
	}

	Edges collect_edges() const
	{
		Edges result;
		for(typename Vertices::const_iterator it=vertices_.begin();it!=vertices_.end();it++)
		{
			const VertexKey& vertex_key_a=it->first;
			const Vertex& vertex=it->second;
			for(typename Vertex::Adjacency::const_iterator jt=vertex.adjacency.begin();jt!=vertex.adjacency.end();jt++)
			{
				const VertexKey& vertex_key_b=jt->first;
				if(vertex_key_a<vertex_key_b)
				{
					result.push_back(std::make_pair(jt->second, std::make_pair(vertex_key_a, vertex_key_b)));
				}
			}
		}
		return result;
	}

	std::string name() const
	{
		return name_;
	}

	void set_name(const std::string& name)
	{
		name_=name;
	}

	std::size_t vertices_count() const
	{
		return vertices_.size();
	}

	std::size_t edges_count() const
	{
		std::size_t adjacencies_count=0;
		for(typename Vertices::const_iterator it=vertices_.begin();it!=vertices_.end();it++)
		{
			adjacencies_count+=it->second.adjacency.size();
		}
		return (adjacencies_count/2);
	}

private:
	Vertices vertices_;
	std::string name_;
};

}

#endif /* GRAPH_H_ */
